//分组背包
#include <iostream>
#include <vector>
using namespace std;
const int MAXV=200;
const int MAXN=30;
const int MAXT=10;
int w[MAXN+1],c[MAXN+1];
vector<int> group[MAXT+1];
int maxc[MAXV+1];

int v,n,t;
int main(){
    cin>>v>>n>>t;
    for(int i=1;i<=n;i++){
        int p;
        cin>>w[i]>>c[i]>>p;
        group[p].push_back(i);
    }

    for(int p=1;p<=t;p++){
        int s=group[p].size();
        for(int v1=v;v1>=0;v1--)
            for(int k=0;k<s;k++){
                int i=group[p][k];
                if (v1>=w[i]){
                    if (maxc[v1-w[i]]+c[i]>maxc[v1]) 
                        maxc[v1]=maxc[v1-w[i]]+c[i];
                }
            }
    }
    cout<<maxc[v];
}